// Copyright 2013 Daniel de Kok
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.gitee.wsl.text.dictomaton

import com.gitee.wsl.ext.list.peek
import com.gitee.wsl.ext.list.pop
import com.gitee.wsl.ext.list.push
import com.gitee.wsl.lang.CompactIntArray
import com.gitee.wsl.lang.bits.BitSet
import com.gitee.wsl.text.format.format

/**
 * A finite state dictionary with perfect hashing, that puts right language cardinalities in states.
 * Dictionaries of this type can are constructed using
 * [DictionaryBuilder.buildPerfectHash].
 *
 * @author Daniel de Kok
 */
internal open class PerfectHashDictionaryStateCard(
    stateOffsets: CompactIntArray, transitionChars: CharArray,
    transitionTo: CompactIntArray, finalStates: BitSet,
    nSeqs: Int
) : DictionaryImpl(stateOffsets, transitionChars, transitionTo, finalStates, nSeqs), PerfectHashDictionary {
    private val d_stateNSuffixes: CompactIntArray

    /**
     * Compute the perfect hash code of the given character sequence.
     *
     * @param seq
     * @return
     */
    override fun number(seq: CharSequence): Int {
        val info = getStateInfo(seq)
        return if (info!!.isInFinalState()) info.hash else -1
    }

    override fun getStateInfo(seq: CharSequence): StateInfo? {
        return getStateInfo(seq, null)
    }

    override fun getStateInfo(seq: CharSequence, startInfo: StateInfo?): StateInfo? {
        val info: StateInfo?

        if (startInfo != null) {
            check(startInfo.isInKnownState) { "Cannot resume transitions from unknown state. Sequence: $seq" }
            info = StateInfo(startInfo.num, startInfo.state, startInfo.trans, startInfo.inFinalState)
        } else {
            info = StateInfo(0, 0, -1, false)
        }

        for (i in 0..<seq.length) {
            val ch: Char = seq[i]
            info.trans = findTransition(info.state, ch)

            if (!info.isInKnownState) {
                return info
            }

            // Count the number of preceding suffixes in the preceding transitions.
            for (j in d_stateOffsets.get(info.state)..<info.trans) info.num += d_stateNSuffixes.get(d_transitionTo.get(j))

            // A final state is another suffix.
            if (d_finalStates.get(info.state)) ++info.num

            info.state = d_transitionTo.get(info.trans)
        }

        info.inFinalState = d_finalStates.get(info.state)

        return info
    }

    /**
     * Compute the sequence corresponding to the given hash code.
     *
     * @param hashCode
     * @return
     */
    override fun sequence(hashCode: Int): String? {
        var hashCode = hashCode
        if (hashCode <= 0) return null

        var state = 0

        // If the hash code is larger than the number of suffixes in the start state,
        // the hash code does not correspond to a sequence.
        if (hashCode > d_stateNSuffixes.get(state)) return null

        val wordBuilder = StringBuilder()

        // Stop if we are in a state where we cannot add more characters.
        while (d_stateOffsets.get(state) != transitionsUpperBound(state)) {
            // Obtain the next transition, decreasing the hash code by the number of
            // preceding suffixes.
            var trans: Int = d_stateOffsets.get(state)
            while (trans < transitionsUpperBound(state)) {
                val stateNSuffixes: Int = d_stateNSuffixes.get(d_transitionTo.get(trans))!!

                if (hashCode - stateNSuffixes <= 0) break

                hashCode -= stateNSuffixes
                ++trans
            }

            // Add the character on the given transition and move.
            wordBuilder.append(d_transitionChars[trans])
            state = d_transitionTo.get(trans)

            // If we encounter a final state, decrease the hash code, since it represents a
            // suffix. If our hash code is reduced to zero, we have found the sequence.
            if (d_finalStates[state]) {
                --hashCode

                if (hashCode == 0) return wordBuilder.toString()
            }
        }

        // Bad luck, we cannot really get here!
        return null
    }


    /**
     * Give the Graphviz dot representation of this automaton. States will also list the
     * number of suffixes 'under' that state.
     *
     * @return
     */
    
    override fun toDot(): String {
        val dotBuilder = StringBuilder()

        dotBuilder.append("digraph G {\n")

        for (state in 0..<d_stateOffsets.size()) {
            for (trans in d_stateOffsets.get(state)..<transitionsUpperBound(state)) dotBuilder.append(
                String.format(
                    "%d -> %d [label=\"%c\"]\n",
                    state, d_transitionTo.get(trans), d_transitionChars[trans]
                )
            )

            if (d_finalStates.get(state)) dotBuilder.append(
                String.format(
                    "%d [peripheries=2,label=\"%d (%d)\"];\n",
                    state,
                    state,
                    d_stateNSuffixes.get(state)
                )
            )
            else dotBuilder.append(
                String.format(
                    "%d [label=\"%d (%d)\"];\n",
                    state,
                    state,
                    d_stateNSuffixes.get(state)
                )
            )
        }

        dotBuilder.append("}")

        return dotBuilder.toString()
    }

    /**
     * @see DictionaryImpl.DictionaryImpl
     */
    init {
        // Marker that indicates that the number of suffixes of a state is not yet computed. We cannot
        // use -1, since CompactIntArray would then require 32-bit per value.
        val magicMarker = nSeqs + 1

        d_stateNSuffixes = CompactIntArray(d_stateOffsets.size(), CompactIntArray.width(magicMarker))
        for (i in 0..<d_stateNSuffixes.size()) d_stateNSuffixes.set(i, magicMarker)

        computeStateSuffixesTopological(0, magicMarker)
    }

    /**
     * Iteratively computes the number of suffixes by topological order
     *
     * @param initialState the root of the graph
     * @param magicMarker  the value in d_stateNSuffixes indicating that the value has not yet been computed
     */
    private fun computeStateSuffixesTopological(initialState: Int, magicMarker: Int) {
        val iterator = sortStatesTopological(initialState).iterator()
        while (iterator.hasNext()) {
            val currentState = iterator.next()

            val currentSuffixes: Int = d_stateNSuffixes.get(currentState)
            if (currentSuffixes == magicMarker) { // is not yet computed
                var trans: Int = d_stateOffsets.get(currentState)
                val transUpperBound: Int = transitionsUpperBound(currentState)
                if (trans < transUpperBound) { // has children
                    var suffixes = if (d_finalStates.get(currentState)) 1 else 0 // add one if current state is final
                    while (trans < transUpperBound) {
                        // add known number of suffixes of children
                        val childState: Int = d_transitionTo.get(trans)
                        require(d_stateNSuffixes.get(childState) != magicMarker) { "suffxies should have been calculated for state " + childState }
                        suffixes += d_stateNSuffixes.get(childState)
                        ++trans
                    }
                    d_stateNSuffixes.set(currentState, suffixes)
                } else {
                    d_stateNSuffixes.set(currentState, if (d_finalStates.get(currentState)) 1 else 0)
                }
            } // else already computed from a different path in the DAG
        }
    }

    private fun sortStatesTopological(initialState: Int): Collection<Int> {
        val reverseTopologicalOrder = ArrayList<Int>(d_stateNSuffixes.size())
        val marked = BooleanArray(d_stateNSuffixes.size())
        val stack/*: Deque<Integer?>*/ = ArrayList<Int>(d_stateNSuffixes.size())
        val head/*: Deque<Integer?>*/ = ArrayList<Int>(d_stateNSuffixes.size())

        stack.push(initialState)
        while (!stack.isEmpty()) {
            val currentState= stack.peek()
            if (currentState == head.peek()) {
                stack.pop()
                head.pop()
                marked[currentState] = true
                reverseTopologicalOrder.add(currentState)
            } else {
                head.push(currentState)
                var trans: Int = d_stateOffsets.get(currentState)
                val transUpperBound: Int = transitionsUpperBound(currentState)
                if (trans < transUpperBound)  // has children
                    while (trans < transUpperBound) {
                        val nextState: Int = d_transitionTo.get(trans)
                        if (!marked[nextState]) {
                            stack.push(nextState)
                        }
                        ++trans
                    }
            }
        }

        return reverseTopologicalOrder
    }


}
